package Aleehot100;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Queue;

/**
 * ClassName: c052
 * Package: Aleehot100
 * Description:994 腐烂的橘子
 *
 * @Author BCXJ
 * @Create 2025/7/31 08:44
 * @Version 1.0
 * @Since 1.0
 */
public class c052 {
    public static void main(String[] args) {
        //int[][] arr = {{2,1,1},{1,1,0},{0,1,1}};
        int[][] arr = {{1},{2},{1},{2}};
        System.out.println(orangesRotting(arr));
    }


    /**
     * 下面的解法是单源的，但很明显这是多源的。
     */
    /*static int res = 0;
    public static int orangesRotting(int[][] grid) {
        res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    grid[i][j] = 1;
                    res += (dfs(grid, i, j, 0) - 1);
                }

            }
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return res;
    }

    private static int dfs(int[][] grid, int i, int j, int curMin) {
        if((i < 0 || i >= grid.length) || (j < 0 || j >= grid[0].length) || grid[i][j] != 1) {
            return curMin ;
        }
        grid[i][j] = 3;
        curMin ++;
        // 上
        int up = dfs(grid, i - 1, j, curMin);
        // 下
        int down = dfs(grid, i + 1, j, curMin);
        // 左
        int left = dfs(grid, i, j - 1, curMin);
        // 右
        int right = dfs(grid, i, j + 1, curMin);
        int max = Math.max(Math.max(up, down), Math.max(left, right));

        System.out.println(max);
        return max;
    }*/


    /*
    class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row: grid) {
            for (int v: row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}
    */

    // 方便上下左右的计算
    static int[] indexRow = {-1, 0 , 1, 0};
    static int[] indexCol = {0 , -1, 0, 1};
    public static int orangesRotting(int[][] grid) {

        HashMap<Integer, Integer> minutesMap = new HashMap<>();// 腐烂的橘子下标(r + c * clen) - 腐烂时间
        Queue<Integer> queue = new ArrayDeque<>(100);

        int rlen = grid.length; // 行长度
        int clen = grid[0].length; // 列长度
        // 遍历 2的元素，有的话放入队列和map 标记时间为0
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 2){
                    queue.add(i * clen + j);
                    minutesMap.put(i * clen + j, 0); // 橘子下标， 腐烂时间
                }
            }
        }

        int ans = 0; // 答案
        // 遍历队列，直到队列无元素
        while(!queue.isEmpty()) {
            int unCode = queue.poll();
            int row = unCode / clen;
            int col = unCode % clen;
            for (int i = 0; i < 4; i++) {
                int r = row + indexRow[i]; // 即将腐烂的下标
                int c = col + indexCol[i];
                if((r >= 0 && r < rlen) && (c >= 0 && c < clen) && grid[r][c] == 1) {// 下标和元素是否合法
                    grid[r][c] = 2; // 元素设置为2，后续检查用
                    queue.add(r * clen + c);
                    minutesMap.put(r * clen + c, minutesMap.get(unCode) + 1); // 感染源头时间基础上 +1
                    ans = minutesMap.get(r * clen + c);
                }
            }
        }

        for (int i = 0; i < rlen; i++) {
            for (int j = 0; j < clen; j++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }

        return ans;
    }
}
